package com.zhangx.datastructure.lineartable;

import java.util.EventListener;
import java.util.Random;

/**
 * @ClassName StaticLinkList
 * @Description 静态链表 P71
 * JAVA的实现跟C不一样，java其实更简单
 * @Author zhangx
 * @Date 2020/12/25 8:45
 **/
public class StaticLinkList {

    /**
     * 数组中有元素的最大值
     */
    private int MAX_SIZE = 6;
//  申请10个，占用5个
    private StaticNode[] staticLinkList = new StaticNode[10];


    static class StaticNode{
        private int data;
        private int cur;
    }

    void initList(){
//        首元素
        StaticNode start = new StaticNode();
//        放6个数据元素
        start.cur = MAX_SIZE + 1;//指向第一个空闲的下标=7
        staticLinkList[0] = start;

//        --------数据节点
//       第一个节点的cur 指向空闲空间的下标->1
//        最后一个节点（头结点）指向第一个有值节点的下标->0 空链表
        for (int i = 1; i < staticLinkList.length - 1; i++) {
            StaticNode node = new StaticNode();
            if (i > MAX_SIZE){
//                其余得初始化，要不然会报错
                node.cur = i + 1;
            }else {
                node.data = i+1;
                node.cur = i+1;
            }
            staticLinkList[i] = node;
        }
//        最后一个数据节点游标指向0
        staticLinkList[MAX_SIZE].cur = 0;//index=6的元素

//        ------尾节点
        StaticNode node = new StaticNode();
        node.data = 0;
        node.cur = 1;//指向第一个有数据的index
        staticLinkList[staticLinkList.length - 1] = node;
    }

    /**
     * 申请空间
     */
    public int malloc(){
//        拿到第一个空闲的下标
        int freeIndex = staticLinkList[0].cur;

        if (staticLinkList[0].cur >0){
//            拿出freeIndex这个元素使用，那么他的下一个元素就是备用的
            staticLinkList[0].cur = staticLinkList[freeIndex].cur;
        }

        return freeIndex;
    }

    /**
     * 见P75的图，很清楚
     * @param node
     * @param index
     */
    public void insert(StaticNode node,int index){

        int newFreeIndex = malloc();
        if (newFreeIndex > 0){
            staticLinkList[newFreeIndex] = node;//将插入的元素放在队尾
            node.cur = index + 1;
            staticLinkList[index].cur = newFreeIndex;

        }

    }

    public void delete(int index){
        staticLinkList[index-1].cur = index + 1;
        free(index);
    }

    public void free(int index){
//        被删除的节点指向原来的空闲节点
        staticLinkList[index].cur = staticLinkList[0].cur;
//        头结点指向删除的空间下标
        staticLinkList[0].cur = index;
    }

    public static void main(String[] args) {
        StaticLinkList staticLinkList = new StaticLinkList();
        staticLinkList.initList();
        StaticNode insertNode = new StaticNode();
        insertNode.data = 99;

//        staticLinkList.insert(insertNode,2);
        staticLinkList.delete(3);
    }
}
